package thired.class10_graph;

import java.util.*;

public class Class04_TopologySort {
    public static List<Node> topologySort(Graph graph){
        HashMap<Node,Integer> inmap = new HashMap<>();
        Queue<Node> zeroQueue = new LinkedList<>();
        List<Node> result = new ArrayList<>();
        for(Node cur :  graph.nodes.values()){
            inmap.put(cur,cur.in);
            if(cur.in == 0){
                zeroQueue.add(cur);
            }
        }
        while (!zeroQueue.isEmpty()){
            Node cur = zeroQueue.poll();
            result.add(cur);
            for(Node next : cur.nexts){
                inmap.put(next,inmap.get(next) - 1);
                if(inmap.get(next) == 0){
                    zeroQueue.add(next);
                }
            }
        }
        return result;
    }
}
